1. Field
An embodiment of the present invention relates to the field of computer-aided design and, more particularly, to routing for integrated circuit designs.
2. Discussion of Related Art
A sequential routing approach is commonly used to determine wire routing for an integrated circuit design. Referring to FIG. 1, for example, a sequential approach may be used to route wires between X and Xxe2x80x2, Y and Yxe2x80x2 and Z and Zxe2x80x2. For purposes of example, it is assumed that there are only three tracks available for routing in the vertical direction and only four tracks in the horizontal direction as indicated by the dotted lines.
A first wire may be routed between X and Xxe2x80x2 as shown. The wire between X and Xxe2x80x2 then becomes an obstacle for all subsequently routed wires. When the route is to be determined for Y and Yxe2x80x2, however, there is no available routing solution within the grid shown. To route Y and Yxe2x80x2 and then Z and Zxe2x80x2, the wire between X and Xxe2x80x2 is ripped up and rerouted.
If the wire between X and Xxe2x80x2 is rerouted as shown in FIG. 2, Y and Yxe2x80x2 may be routed as shown, but there is then no available routing solution for Z and Zxe2x80x2. Both of the wires shown in FIG. 2 are then ripped up and rerouted. Ripping up and rerouting wires can be time and resource intensive and may still not select a globally optimal routing for the wires to be routed. Further, even where rip-up-re-routing is not necessary or where it is used and successful in routing all of the desired wires, because of the sequential nature of the routing, the routing selected for the first wire may cause less desirable routings to be selected for subsequent wires.
Referring to FIG. 3, sequential routing may also be used to route multi-terminal nets. For one approach, a minimal spanning tree (indicated by the dotted line) may be used to identify the shortest distance between each of the terminals A, B, C and D in the net of FIG. 3. The wire between A and B may be routed first, followed by the wire between B and C and the wire between C and D. The routing for each of these wires is selected sequentially, with little if any information about subsequent wires to be routed. Thus, this type of routing approach may also not provide a globally optimized solution.
Objective-driven routing is another routing approach in which objectives (also referred to as cost functions) such as density, timing, congestion, jog and/or cross-talk, for example, may be specified. Objective-driven routers, to the extent possible, determine wire routes according to the specified objective(s). Currently available objective-driven routers, however, may not do an acceptable job of mixing together multiple objectives that may indicate conflicting results.
Controllability may also be an issue for some objective-driven routers. Conventional objective-driven routers typically do not provide for designers to select objectives on the fly. Thus, if a routing pass begins with a first specified objective, it may not be straightforward to change objectives without having to perform the entire routing pass again.